/*
 * @lc app=leetcode.cn id=17 lang=golang
 * @lcpr version=30118
 *
 * [17] 电话号码的字母组合
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	m := map[rune][]rune{
		'2': {'a', 'b', 'c'},
		'3': {'d', 'e', 'f'},
		'4': {'g', 'h', 'i'},
		'5': {'j', 'k', 'l'},
		'6': {'m', 'n', 'o'},
		'7': {'p', 'q', 'r', 's'},
		'8': {'t', 'u', 'v'},
		'9': {'w', 'x', 'y', 'z'},
	}
	res := make([]string, 0)
	dfs(digits, 0, "", m, &res)
	return res
}

func dfs(digits string, index int, path string, m map[rune][]rune, res *[]string) {
	if index == len(digits) {
		*res = append(*res, path)
		return
	}
	for _, v := range m[rune(digits[index])] {
		dfs(digits, index+1, path+string(v), m, res)
	}
}

// @lc code=end

/*
// @lcpr case=start
// "23"\n
// @lcpr case=end

// @lcpr case=start
// ""\n
// @lcpr case=end

// @lcpr case=start
// "2"\n
// @lcpr case=end

*/

